package 每日一题;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/stone-game-ix/
 * @since 2022/1/20
 */
public class _2029_石子游戏IX {
    /**
     * 博弈论
     * 所有石子分为 0 1 2 这三种类型的石子，先分析 类型为0的石子
     * 类型0 ： 类型0则代表双方只是交换手，对于总数并没有实际的变化
     *      如果 cnt0 为偶数  则结果相当于没有cnt0的结果
     *      如果 cnt0 为奇数  则结果相当于只有一个cnt0的结果
     * 类型1/类型2 ：
     *      如果Alice 先移除的是 cnt1 则移动顺序为 112121212.....
     *      如果 cnt1 恰好为1个 则也还是 Alice 胜利
     *      如果 cnt1 的数量小于或等于 cnt2 的数量，如果小于 则Alice胜利
     *      反之 cnt1 的数量大于 cnt2 的数量 则Bob胜利 （如果多的数量大于2个 是没有可移除的，其余情况为石子用完）
     *
     *      如果Alice 先移除的是 cnt2 则移动顺序为 221212121.....
     *      与上方解析同理
     *
     *  细节 ： 如果 cnt0 为偶数
     *          第一种情况下是 当 cnt1 == 1 && cnt2 >= 1
     *          第二种情况下是 当 cnt2 == 1 && cnt1 >= 1
     *          即 (cnt1 == 1 && cnt2 >= 1) || (cnt1 >= 1 && cnt2 == 1)
     *          ----->  cnt1 >= 1 && cnt2 >= 1
     *
     *          如果 cnt0 为奇数
     *          则交换手 即先手为Bob  就需要将上方分析类型1/2反过来 并且保证石子不可用完
     *          即当 cnt1 - cn2 > 2 || cnt2 - cnt1 > 2 即为Alice胜利
     * @param stones 目标石子数组
     * @return boolean
     */
    public boolean stoneGameIX(int[] stones) {
        int cnt0 = 0, cnt1 = 0, cnt2 = 0;
        // 遍历计算 cnt0 cnt1 cnt2 的总数
        for (int stone : stones) {
            int type = stone % 3;
            if (type == 0) {
                ++cnt0;
            } else if (type == 1) {
                ++cnt1;
            } else {
                ++cnt2;
            }
        }
        // cnt0 为偶数的情况
        if (cnt0 % 2 == 0) {
            return cnt1 >= 1 && cnt2 >=1;
        }
        // cnt0 为奇数的情况
        return cnt1 - cnt2 > 2 || cnt2 - cnt1 > 2;
    }
}
